package com.nanbei.dp;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @ClassDescription: Catalan数 (二叉树的数目)
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/10 14:26
 */
public class Catalan {
    /*
        Catalan数有许多重要的性质和应用，以下是一些主要的例子：
            二叉树的数目：有 n+1 个节点的不同二叉树的数目。
            正确括号序列的数目：由 n 对括号组成的合法括号序列的数目。
            凸多边形的三角剖分数：一个 (n+2) 边形的不同三角剖分数目。
            栈操作序列：将一个有序序列压入栈并弹出的不同操作序列数目，使得弹出序列仍然有序。

            1           1

            2           1               2
                         \             /
                          2           1

            3       1       1            2         3         3
                      \      \          / \       /         /
                       3      2        1   3     1         2
                       /       \                  \       /
                      2         3                  2     1

             c(0) = 1
             c(1) = 1
             c(2) = c(0)*c(1) + c(1)*c(0)
             c(3) = c(0)*c(2) + c(1)*c(1) + c(2)*c(0)
             c(4) = c(0)*c(3) + c(1)*c(2) + c(2)*c(1) + c(3)*c(0)
             c(5) = c(0)*c(4) + c(1)*c(3) + c(2)*c(2) + c(3)*c(1) + c(4)*c(0)
             ......
     */

    public static void main(String[] args) {
        System.out.println(getCatalan(6));
    }

    public static int getCatalan(int num){
        // 用来存放下边对应的catalan数
        int[] dp = new int[num + 1];
        dp[0] = 1;
        dp[1] = 1;
        // 计算下标为J的Catalan数
        for (int j = 2; j < num + 1; j++) {
            // 用 < j的Catalan数计算当前的Catalan数
            for (int i = 0; i < j; i++) {
                dp[j] += dp[i]*dp[j-1-i];
                System.out.printf("(%d,%d)\t",i,j-1-i);
            }
            System.out.println();
            System.out.println(Arrays.toString(dp));
            System.out.println();
        }
        ArrayList<String[]> dp1 = new ArrayList<>();
        return dp[num];
    }


}
